package com.gitee.ywj1352.算法.week04;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 假设一个二叉搜索树具有如下特征：
 * <p>
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 验证二叉搜索树 {


    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);
        t5.left = t3;
        t5.right = t8;
        t3.left = t2;
        t3.right = t4;
        t2.left = t1;
        t8.left = t6;
        t8.right = t7;

        boolean validBST = isValidBST2(t5);

        System.out.println(validBST);


    }


    public static int pre = Integer.MIN_VALUE;

    public static boolean isValidBST2(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST2(root.left)) return false;
        if (root.val <= pre) return false;
        pre = root.val;
        if (!isValidBST2(root.right)) return false;
        return true;
    }

    public static boolean isValidBST3(TreeNode root) {
        if (root == null) return true;
        List<Integer> res = new ArrayList<>();
        middle(root, res);
        if (res.size() < 2) return true;
        for (int i = 1; i < res.size(); i++) {
            if (res.get(i - 1) > res.get(i)) return false;
        }
        return true;
    }

    public static void middle(TreeNode root, List<Integer> res) {
        if (root == null) return;
        middle(root.left, res);
        res.add(root.val);

        middle(root.right, res);
    }


    /**
     * 验证 二叉搜索树
     *
     * @param root
     * @return
     */
    public static boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }


    static boolean helper(TreeNode root, Integer lower, Integer upper) {
        if (root == null) return true;
        int val = root.val;
        if (lower != null && lower >= val) return false;
        if (upper != null && upper <= val) return false;

        if (!helper(root.left, lower, val)) return false;
        if (!helper(root.right, val, upper)) return false;
        return true;
    }

}
